#include <bits/stdc++.h>
using namespace std;

#define MAXN 200001

struct Segmenttree {
    int lc, rc, sum;
} tr[MAXN * 32];

int n, m, cnt, idx, a[MAXN], ind[MAXN * 2];
int q[MAXN];

int build(int s, int t)
{
    int x = ++idx;
    tr[x].sum = 0;
    if (s == t)
        return x;
    int mid = (s + t) >> 1;
    tr[x].lc = build(s, mid);
    tr[x].rc = build(mid + 1, t);
    return x;
}

int insert(int cur, int l, int r, int x, int s)
{
    int k = ++idx;
    tr[k] = tr[cur];
    if (l == r) {
        tr[k].sum += s;
        return k;
    }
    int mid = (l + r) >> 1;
    if (x <= mid)
        tr[k].lc = insert(tr[k].lc, l, mid, x, s);
    else
        tr[k].rc = insert(tr[k].rc, mid + 1, r, x, s);
    tr[k].sum = tr[tr[k].lc].sum + tr[tr[k].rc].sum;
    return k;
}

int query(int p, int q, int l, int r, int k)
{
    if (l == r)
        return l;
    int mid = (l + r) >> 1;
    int left_sum = tr[tr[q].lc].sum - tr[tr[p].lc].sum;
    if (k <= left_sum)
        return query(tr[p].lc, tr[q].lc, l, mid, k);
    else
        return query(tr[p].rc, tr[q].rc, mid + 1, r, k - left_sum);
}

int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) {
        scanf("%d", a + i);
        ind[i] = a[i];
    }
    cin >> m;
    cnt = 0;
    for (int i = 1; i <= m; i++) {
        string s;
        cin >> s;
        if (s == "add") {
            cin >> q[i];
            ind[++cnt + n] = q[i];
        } else {
            q[i] = -1;
        }
    }
    sort(ind + 1, ind + n + cnt + 1);
    int len = unique(ind + 1, ind + n + cnt + 1) - ind - 1;

    int rt_empty = build(1, len);
    int cur = rt_empty;
    for (int i = 1; i <= n; i++) {
        int pos = lower_bound(ind + 1, ind + len + 1, a[i]) - ind;
        cur = insert(cur, 1, len, pos, 1);
    }

    int tot = n;
    for (int i = 1; i <= m; i++) {
        if (q[i] != -1) {
            int pos = lower_bound(ind + 1, ind + len + 1, q[i]) - ind;
            cur = insert(cur, 1, len, pos, 1);
            tot++;
        } else {
            int k = (tot + 1) / 2;
            int pos_index = query(rt_empty, cur, 1, len, k);
            printf("%d\n", ind[pos_index]);
        }
    }
    return 0;
}